package jm.data.structure.tree;

import jm.data.structure.tree.printer.BinaryTreeInfo;

import java.util.LinkedList;
import java.util.Queue;

/**
 * @Description 二叉树
 * @date 2022/4/10 9:01
 */
@SuppressWarnings({"all"})
public class BinaryTree<E> implements BinaryTreeInfo {

    // 节点数量
    protected int size;

    // 根节点
    protected Node<E> root;

    // 节点类
    protected static class Node<E>{
        // 元素值
        E e;
        // 左子节点
        Node<E> left;
        // 右子节点
        Node<E> right;
        // 父节点
        Node<E> parent;
        public Node(E e, Node<E> parent){
            this.e = e;
            this.parent = parent;
        }
        /**
         * 判断当前节点是否是叶子节点
         * @return
         */
        protected boolean isLeaf(){
            return left == null && right == null;
        }

        /**
         * 判断当前节点是否存在左右子节点
         * @return
         */
        protected boolean hasTwoChildren(){
            return left != null && right != null;
        }

        /**
         * 判断是不是父节点的左子树
         * @return
         */
        public boolean isLeftChild(){
            return parent != null && this == parent.left;
        }

        /**
         * 判断是不是父节点的右子树
         * @return
         */
        public boolean isRightChild(){
            return parent != null && this == parent.right;
        }

        /**
         * 返回兄弟节点
         * @return
         */
        public Node<E> sibling(){
            if (isLeftChild()){
                return parent.right;
            }
            if (isRightChild()){
                return parent.left;
            }
            return null;
        }

        @Override
        public String toString() {
            return "Node{" +
                    "e=" + e +
                    ", left=" + left +
                    ", right=" + right +
                    ", parent=" + parent +
                    '}';
        }
    }

    // visitor抽象类：用于遍历时对返回的值进行处理。
    public static abstract class Visitor<E> {

        // 在递归时保存上一次返回值，判断是否停止递归
        boolean stop;

        /**
         * @param e
         * @return ture：停止遍历
         */
        public abstract boolean visit(E e);
    }

    /**
     * 创建节点接口
     * @param e
     * @param parent
     * @return
     */
    protected Node<E> createNode(E e, Node<E> parent){
        return new Node<>(e,parent);
    }

    /**
     * 获取元素数量
     * @return
     */
    public int size(){
        return size;
    }

    /**
     * 判断元素是否为空
     * @return
     */
    public boolean isEmpty(){
        return size == 0;
    }

    /**
     * 清空树
     */
    public void clear(){
        root = null;
        size = 0;
    }

    /**
     * 前序遍历
     * @param visitor 调用实现逻辑
     */
    public void preorderTraversal(Visitor<E> visitor){
        if (visitor == null){
            return;
        }
        preorderTraversal(root,visitor);
    }

    private void preorderTraversal(Node<E> node,Visitor<E> visitor){
        if (node == null || visitor.stop){
            return;
        }
        visitor.stop = visitor.visit(node.e);
        preorderTraversal(node.left,visitor);
        preorderTraversal(node.right,visitor);
    }

    /**
     * 中序遍历
     * @param visitor 调用实现逻辑
     */
    public void inorderTraversal(Visitor<E> visitor){
        if (visitor == null){
            return;
        }
        inorderTraversal(root,visitor);
    }

    private void inorderTraversal(Node<E> node,Visitor<E> visitor){
        if (node == null || visitor.stop){
            return;
        }
        inorderTraversal(node.left,visitor);
        if (visitor.stop){
            return;
        }
        visitor.stop = visitor.visit(node.e);
        inorderTraversal(node.right,visitor);
    }

    /**
     * 后序遍历
     * @param visitor 调用实现逻辑
     */
    public void postorderTraversal(Visitor<E> visitor){
        if (visitor == null){
            return;
        }
        postorderTraversal(root ,visitor);
    }

    private void postorderTraversal(Node<E> node,Visitor<E> visitor){
        if (node == null || visitor.stop){
            return;
        }
        postorderTraversal(node.left,visitor);
        postorderTraversal(node.right,visitor);
        if (visitor.stop){
            return;
        }
        visitor.stop = visitor.visit(node.e);
    }

    /**
     * 层序遍历
     * @param visitor 调用实现逻辑
     */
    public void levelOrderTraversal(Visitor<E> visitor){
        if (root == null || visitor == null) {
            return;
        }
        Queue<Node<E>> queue = new LinkedList<>();
        queue.offer(root);
        while (!queue.isEmpty()){
            Node<E> node = queue.poll();
            // 如果等于 true 直接退出循环
            if (visitor.visit(node.e)) {
                return;
            }
            if (node.left != null){
                queue.offer(node.left);
            }
            if (node.right != null){
                queue.offer(node.right);
            }
        }
    }

    /**
     * 获取二叉树高度
     * @return 高度
     */
    public int height(){
        return height(root);
    }

    private int height(Node<E> node){
        if (node == null){
            return 0;
        }
        // 根节点的高度等于它的左子节和右子节点之间的高度的最大值加一
        return 1 + Math.max(height(node.left),height(node.right));
    }

    /**
     * 迭代获取高度
     * @return
     */
    public int heightIterator(){
        if (root == null) {
            return 0;
        }
        int height = 0;
        // 记录每一层元素的数量
        int levelSize = 1;
        Queue<Node<E>> queue = new LinkedList<>();
        queue.offer(root);
        while (!queue.isEmpty()){
            Node<E> node = queue.poll();
            levelSize--;

            if (node.left != null){
                queue.offer(node.left);
            }
            if (node.right != null){
                queue.offer(node.right);
            }
            // 等于0表示当前层访问完毕。
            if (levelSize == 0){
                levelSize = queue.size();
                height++;
            }
        }
        return height;
    }

    /**
     * 判断树是否为完全二叉树
     * @return
     */
    public boolean isComplete(){
        if (root == null){
            return false;
        }
        Queue<Node<E>> queue = new LinkedList<>();
        queue.offer(root);

        boolean leaf = false;
        while (!queue.isEmpty()){
            Node<E> node = queue.poll();

            if (leaf && !node.isLeaf()){
                return false;
            }

            if (node.left != null){
                queue.offer(node.left);
            }else if(node.right != null){
                return false;
            }

            if (node.right != null){
                queue.offer(node.right);
            }else {
                // 只要出现右侧为空的情况，后面遍历的所有节点都需要是叶子节点
                leaf = true;
            }

        }
        return true;
    }

    /**
     * 获取当前节点的前驱节点
     * @param node
     * @return
     */
    public Node<E> predecessor(Node<E> node){
        if (node == null) {
            return null;
        }
        Node<E> prev = node.left;

        // 前驱在左子树中
        if (prev != null){
            while (prev.right != null){
                prev = prev.right;
            }
            return prev;
        }

        // 前驱在祖父节点中
        while (node.parent != null && node == node.parent.left){
            node = node.parent;
        }
        // 直接返回node.parent即可
        // 1. node.parent == null;
        // 2. node == node.parent.right;
        return node.parent;
    }

    /**
     * 获取后继节点
     * @param node
     * @return
     */
     public Node<E> successor(Node<E> node){
        if (node == null) {
            return null;
        }
        Node<E> prev = node.right;

        // 前驱在左子树中
        if (prev != null){
            while (prev.left != null){
                prev = prev.left;
            }
            return prev;
        }

        // 前驱在祖父节点中
        while (node.parent != null && node == node.parent.right){
            node = node.parent;
        }
        return node.parent;
    }

        @Override
        public Object root() {
            return root;
        }

        @Override
        public Object left(Object node) {
            return ((Node<E>)node).left;
        }

        @Override
        public Object right(Object node) {
            return ((Node<E>)node).right;
        }

        @Override
        public Object string(Object node) {
            return ((Node<E>)node).e;
        }
}
